In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in the general resource allocation problem. The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm under two different models, stochastic input and random permutation, with minimal technical assumptions on the input data.

Weaknesses: - My primary concern is insufficient comparison with the existing literature on online LP, like the two works cited [Agrawal '14, Kesselheim et al. '14]: - The paper claims novelty in the sublihear competitive ratios obtained in those works of the form O(1 - \eps(m,n)), so that \eps(m,n) * OPT is the regret. From a glance at the works cited by [Agrawal '14], "Online stochastic packing applied to display ad allocation" [Feldman et al. '10] has an 1/OPT term in this competitive ratio, giving a sublinear regret bound. Some clarifying discussion is necessary here. Some discussion and a clearer comparison is necessary, since this line of work is so well-established. Some clarification about this would be appreciated; in any case, the manuscript should discuss this at greater depth.

The analysis of the algorithm is conducted under two models: stochastic inputs (columns of LP drawn i.i.d.) and random permutation model (columns of LP revealed in a random order). The authors develop a simple and fast online algorithm performing stochastic subgradient descent on a dual problem with provable guarantees on the regret and constraint violation. The paper received borderline reviews with a slight lean towards acceptance. The main strengths of the paper are: - New techniques for deriving the regret bounds in the random permutation model (permutational Rademacher complexity). The main weaknesses were: - Insufficient comparison with the existing online LP literature, in particular with the competitive ratio bounds of previous work.

In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in the general resource allocation problem. The algorithm requires only one single pass through the input data and is free of doing any matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it essentially performs (one-pass) projected stochastic subgradient descent in the dual space. We analyze the algorithm under two different models, stochastic input and random permutation, with minimal technical assumptions on the input data.